1. Field of the Invention
This invention relates generally to automatic partitioning of graphs and more particularly to automatic partitioning of communication networks and other physical systems.
2. Discussion of the Related Art
Many physical systems can be modeled by a graph. These include communication networks, distributed computing systems, production systems and printed circuit board layouts.
Graph partitioning belongs to a class of problems called NP-complete problems (Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, W.H. Freeman and Co., 1979). An NP-complete problem is a problem which can only be solved by the complete enumeration of all the feasible solutions (i.e., those that satisfy all the constraints imposed on the problem) from which the best solution will be chosen. This is a very inefficient method of solving large problems. Unfortunately, there is no known efficient method of solving this class of problems, and this has often necessitated the use of heuristic methods. Heuristic methods are intended to produce good, but not necessarily optimal, solutions.
One of the earliest methods of solving the problem is the spectral partitioning method (Pothen, A. et al., xe2x80x9cPartitioning Sparse Matrices with Eigenvectors of Graphs,xe2x80x9d SIAM J. of Matrix Analysis. and Applications, 11(3):430-452 (1990); Hendrickson, B. and R. Leland, xe2x80x9cA Multilevel Algorithm for Partitioning Graphs,xe2x80x9d Technical Report, SAND93-1301, Sandia National Labs (1993)). However, this method is very expensive since it requires the computation of the eigenvector corresponding to the second smallest eigenvalue. Thus, the method is limited in practice to graphs of very small sizes.
Another method of solving the problem is the geometric partitioning method (Miller, G. et al., xe2x80x9cA Unified Geometric Approach to Graph Separators,xe2x80x9d Proc of 31st Annual Symposium on Foundation of Computer Sci., 538-547 (1991); Heath, M. and P. Raghavan, xe2x80x9cA Cartesian Nested Dissection Algorithm,xe2x80x9d Tech. Report UIUCDCS-R-92-1772, Dept. of Computer Sci., Univ. of Ill., Urbana, Ill. (1992); Nour-Omid, B. et al., xe2x80x9cSolving Finite Element Equations on Concurrent Computers,xe2x80x9d Am. Soc. of Mech. Engineers, 291-307, (A. K. Noor, ed. 1986)). However, this method provides partitions that are worse than those of the spectral method. A major limitation of this method is that it requires knowledge of the coordinates of the vertices of the graph. Unfortunately, in many areas, such as communication networks and VLSI design, there is no geometry or xe2x80x9ccoordinatesxe2x80x9d associated with the graph.
A multilevel partitioning method has also been proposed (Bui, T. and C. Jones, xe2x80x9cA Heuristic for Reducing Fill in Sparse Matrix Factorization,xe2x80x9d Proc. of 6th SIAM Conf. on Parallel Processing for Scientific Computing, 445-452 (1993); Cheng, C. and Y. Wei, xe2x80x9cAn Improved Two-way Partitioning Algorithm with Stable Performance,xe2x80x9d IEEE Trans on Computer-Aided Design, 10(12):1502-1511 (1991); Hagen, L. and A. Kahng, xe2x80x9cFast Spectral Method for Ratio Cut Partitioning and Clustering,xe2x80x9d Proc of IEEE International Conf on Computer-Aided Design, 10-13 (1991); Hagen, E. and A. Kahng, xe2x80x9cA New Approach to Effective Circuit Clustering,xe2x80x9d Proc of IEEE International Conf on Computer-Aided Design, 422-427 (1992); Garbers, J. et al., xe2x80x9cFinding Clusters in VLSI Circuits,xe2x80x9d Proc. of IEEE International Confon Computer-Aided Design, 520-523 (1990); Karypis, G. and V. Kumar, xe2x80x9cA Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,xe2x80x9d Technical Report 95-035, Dept. of Computer Sci., Univ of Minn., Minnesota, Minn. (1995)). This method coarsens the graph (i.e., reduces the size of the graph) by collapsing the nodes and edges; it partitions the smaller graph, and then uncoarsens it to construct a partition of the original graph. Unfortunately this method is very complicated and has not yet been shown to be better than the other two methods.
In all the above methods, it is assumed that the graph is not weighted. This means that all the nodes are essentially identical and the only objective is to partition the graph to generate an equal number of nodes in each partition. When weights are associated with either the nodes or the edges, none of these methods will work adequately. Moreover, the cost of solving the problem will be very high. None of these methods has been proposed for use in a communication network.
The present invention is a method for automatically partitioning node-weighted, edge-constrained graphs. In contrast with the prior art, the present invention automatically manipulates the nodes of a graph to partition the graph without the need for manually configuring each node. The present invention uses a software control mechanism to partition the graph and, if necessary, to re-partition the graph, without the need to manually intervene in the configuration of the network.
According to one embodiment of the present invention, a method is provided for partitioning a network comprising modeling the network as a graph comprising nodes which represent network devices, and edges which represent links between the devices, and automatically partitioning the graph into domains. Preferably, the method further includes a step of assigning a weight to each node in the graph, and the partitioning step includes balancing partitions as a function of the weight of each node in a respective partition.
In another embodiment of the invention, a method is provided for developing a partitioning scheme for a communication network having a plurality of interconnected devices. The method includes automatically determining a topology of the communication network, automatically partitioning the communication network into a number of domains, each including a number of the plurality of devices, and informing each of the number of devices in each of the domains of partitioning information.
In another embodiment of the invention, a method is provided for automatically partitioning a graph into domains, the graph having a plurality of nodes interconnected by a plurality of edges. The method includes identifying a number of anchor nodes in the graph, combining the nodes into a number of control groups which number is the same as the number of domains, such that each control group includes only one anchor node.
In yet another embodiment of the invention, a method is provided for operating a partitioned communication network having a plurality of network devices interconnected by a plurality of communication links. The method comprises detecting a failure of a network device, automatically generating a new partition based on a topology of the network without the failed device and operating the communication network using the automatically-generated partition. The automatic generating step includes determining the topology of the network without the failed device. The topology is a graph representation of the communication network having nodes representing the network devices and edges representing the communication links. The method further includes identifying supernodes in the graph representation, forming a plurality of clusters of nodes based on the identified supernodes and generating new domains based on the clusters.
Such an automated system has the advantage that it can have a built-in mechanism that allows the network control agents to monitor one another""s status. They cooperatively take over the control of a domain whose control agent has failed. Similarly, when the failed device comes up again, the other agents relinquish control of its domain.
Another advantage of an automated system is load balancing. A manually configured system is generally static and does not respond easily to the load changes in the system. An automated system partitions the system into as many domains as there are available control agents and ensures that each agent has a fair share of the load (or traffic). Typically, there is in the background a continuous monitoring of the load distribution among the different agents and the domain boundaries are periodically adjusted to reflect the changes in the system.
In yet another embodiment of the invention, a domain partitioning engine is provided which includes means for receiving a representation of a graph comprising nodes and edges, means for identifying supernodes and means, responsive to the means for identifying, for automatically partitioning the graph into a number of domains. Preferably, the engine further comprises means for assigning a weight to each node in the graph, and the means for partitioning includes means for balancing the partitions as a function of the weights of each node in a respective partition.
In yet another embodiment of the invention, a method for automatically partitioning graphs is provided, wherein a number of anchor nodes are identified, supernodes are formed from nodes in the graph and clusters are formed from the supernodes around each of the anchor nodes, such that each cluster includes only one anchor node. The weights of the clusters are balanced and domains are generated from the clusters.
These and other features and advantages shall appear from the following detailed description of the present invention.